// 岛屿数量

package Leetcode;

import java.util.LinkedList;

// 深度优先遍历DFS
class solution_200_1 {
    public int numIslands(char[][] grid) {
        int xx = grid.length;
        int yy = grid[0].length;
        int result = 0;

        for (int i = 0; i < xx; i++)
            for (int j = 0; j < yy; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }

        return result;
    }

    public void dfs(char[][] grid, int x, int y) {
        int xx = grid.length;
        int yy = grid[0].length;

        // 如果越界或者为0则停止
        if (x < 0 || x >= xx || y < 0 || y >= yy || grid[x][y] == '0')
            return;

        // 没越界且值为1
        grid[x][y] = '0';

        // 遍历周围四个点
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);

    }
}

// 广度优先遍历DFS
class solution_200_2 {
    public int numIslands(char[][] grid) {
        int xx = grid.length;
        int yy = grid[0].length;
        int result = 0;

        LinkedList<int[]> queue = new LinkedList<>();

        for (int i = 0; i < xx; i++)
            for (int j = 0; j < yy; j++) {
                // 如果值为1
                if (grid[i][j] == '1') {
                    result++;
                    queue.addLast(new int[] { i, j });
                    while (!queue.isEmpty()) {
                        int[] index = queue.pollFirst();
                        if (index[0] < 0 || index[0] >= xx || index[1] < 0 || index[1] >= yy
                                || grid[index[0]][index[1]] == '0')
                            continue;
                        grid[index[0]][index[1]] = '0';
                        queue.addLast(new int[] { index[0] - 1, index[1] });
                        queue.addLast(new int[] { index[0] + 1, index[1] });
                        queue.addLast(new int[] { index[0], index[1] - 1 });
                        queue.addLast(new int[] { index[0], index[1] + 1 });
                    }
                }
            }
        return result;
    }
}

// 并查集
class solution_200_3 {
    class UnionFind {
        int result;
        int[] parent; // 记录该节点的双亲结点，用于查找该结点的根结点
        int[] rank; // 记录以该结点为根结点的树的深度，主要用于优化，在合并两个集合的时候，rank大的集合合并rank小的集合

        public UnionFind(char[][] grid) {
            result = 0;
            int xx = grid.length;
            int yy = grid[0].length;
            parent = new int[xx * yy];
            rank = new int[xx * yy];

            for (int i = 0; i < xx; i++)
                for (int j = 0; j < yy; j++) {
                    // 值为1的点的双亲结点是它自己
                    if (grid[i][j] == '1') {
                        result++;
                        parent[i * yy + j] = i * yy + j;
                    }
                    // 初始所有结点秩都为0
                    rank[i * yy + j] = 0;
                }
        }

        public int find(int i) {
            return parent[i] == i ? parent[i] : find(parent[i]);
        }

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            // 如果两个点的根结点不同
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty])
                    parent[rooty] = rootx;
                else if (rank[rootx] < rank[rooty])
                    parent[rootx] = rooty;
                // 如果秩相同，不论怎么连接最终的秩都会加一
                else {
                    parent[rootx] = rooty;
                    rank[rooty] += 1;
                }
                // 由于合并了两个1所以数量减1
                result--;
            }
        }

        public int getResult() {
            return result;
        }
    }

    public int numIslands(char[][] grid) {
        int xx = grid.length;
        int yy = grid[0].length;
        UnionFind uf = new UnionFind(grid);

        for (int i = 0; i < xx; i++)
            for (int j = 0; j < yy; j++) {
                if (grid[i][j] == '1') {
                    // 这里置0是为了防止重复遍历
                    grid[i][j] = '0';
                    // 组合四个邻接点
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                        uf.union(i * yy + j, (i - 1) * yy + j);
                    }
                    if (i + 1 < xx && grid[i + 1][j] == '1') {
                        uf.union(i * yy + j, (i + 1) * yy + j);
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                        uf.union(i * yy + j, i * yy + j - 1);
                    }
                    if (j + 1 < yy && grid[i][j + 1] == '1') {
                        uf.union(i * yy + j, i * yy + j + 1);
                    }
                }
            }
        return uf.getResult();
    }
}